/**
 * 
 */
package leetCode;

import java.util.Stack;

/**
 * @author zhong
 *
 */
public class DailyTemperatures {
	public int[] dailyTemperatures(int[] temperatures) {
		int n = temperatures.length;
		int[] res = new int[n];
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < res.length; i++) {
			while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
				int pos = stack.pop();
				res[pos] = i - pos;
			}
			stack.push(i);
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
		int res[] = new DailyTemperatures().dailyTemperatures(temperatures);
		for (int i = 0; i < res.length; i++) {
			System.out.println(res[i]);
		}
		System.out.println();
	}

}
